package leetcode.editor.cn;

/**
 * 计数排序：https://blog.csdn.net/qq_42111463/article/details/84146915
 */
public class ACountingSort implements AIOrder{
    @Override
    public void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int min = nums[0];
        int max = nums[0];
        for (int num : nums) {
            if (num < min) {
                min = num;
            } else if (num > max) {
                max = num;
            }
        }

        int[] arrys = new int[max-min+1];
        for (int num : nums) {
            arrys[num-min]++;
        }

        int circle = 0;
        for (int i = 0; i < arrys.length; i++) {
            for (int j = 0; j < arrys[i]; j++) {
                nums[circle++] = min+i;
            }
        }
    }

    public static void main(String[] args) {
        AIOrder order = new ACountingSort();
        int[] nums = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0, 7};
        order.sort(nums);
        System.out.println("end");
    }
}
